package utils;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map.Entry;

import myinterface.INoeud;


public class Graphe {

	private HashMap<Integer,Polygon> polygones;
	private HashMap<Integer,Segment> chemins;
	
	
	/**
	 * Construction du graphe. Je suppose pour le moments que l'on reçoit des polygones qui connaissent leur chemin et ainsi de suite
	 * @param polygones
	 * @param segments
	 */
	public Graphe(List<Polygon> polygones,List<Segment> segments){

		this.polygones = new HashMap<Integer,Polygon>();
		this.chemins = new HashMap<Integer,Segment>();

		for(Polygon poly : polygones)
			this.polygones.put(poly.getId(), poly);

		for(Segment seg : segments)
			this.chemins.put(seg.getId(), seg);
	}

	public String toString(){
		StringBuffer st = new StringBuffer("<map>\n");

		for(Entry<Integer, Polygon> entry : polygones.entrySet()) 
			st.append(entry.getValue().toString()+"\n\n");

		for(Entry<Integer, Segment> entry2 : chemins.entrySet()) 
			st.append(entry2.getValue().toString()+"\n\n");

		st.append("</map>");
		return st.toString();
	}

	
	private static double poids(Point p,Point p2)  { 
		/*
		double a = Math.PI / 180;
		double lat1 = p.getX() * a;
		double lat2 = p2.getX() * a; 
		double lon1 = p.getY() * a;
		double lon2 = p2.getY() * a;
		double t1 = Math.sin(lat1) * Math.sin(lat2);
		double t2 = Math.cos(lat1) * Math.cos(lat2);
		double t3 = Math.cos(lon1 - lon2);
		double t4 = t2 * t3; 
		double t5 = t1 + t4;
		double rad_dist = Math.atan(-t5/Math.sqrt(-t5 * t5 +1)) + 2 * Math.atan(1);
		return Math.abs((rad_dist * 3437.74677 * 1.1508) * 1.6093470878864446); 
		*/
		
		return Math.sqrt(Math.pow(p2.getX() - p.getX(), 2) + Math.pow(p2.getY() - p.getY(), 2) );
	}


	
	/**
	 * Trouve le plus court chemin entre 2 noeud du graphe, par exemple d'un batiment à un autre
	 * @param source
	 * @param puit
	 * @return
	 */
	public List<INoeud> plusCourtChemin(INoeud source, INoeud puit){
		double [] distance =  new double[this.chemins.size()];
		double poids,poids2;
		Segment s1,s2;

		// Initialisation
		for(int i = 0 ; i < distance.length ; i++)
			distance[i] = Double.MAX_VALUE;

		boolean [] parcouru = new boolean[this.chemins.size()];

		for(int i = 0 ; i < parcouru.length ; i++)
			parcouru[i] = false;

		for(int i = 0 ; i < source.getChemin().size(); i++)
			distance[source.getChemin().get(i)] = 0 ;

		// On parcours tous les noeuds
		while(!allParcouru(parcouru)){
			s1 = trouve_min(parcouru,distance);
			parcouru[s1.getId()] = true;
			poids2 = poids(s1.getDebut(),s1.getFin());
			for(int i = 0 ; i < s1.getCroisements().size(); i++){
				s2 = this.chemins.get(s1.getCroisements().get(i));
				poids = poids2 + poids(s2.getDebut(),s2.getDebut());
				if(distance[s2.getId()] > distance[s1.getId()] + poids){
					distance[s2.getId()] = distance[s1.getId()] + poids;
				}
			}
		}

		// Retrouver le chemin
		ArrayList<INoeud> chemin = new ArrayList<INoeud>();
		chemin.add(puit);
		Segment tmp;
		boolean trouve = false;
		tmp = trouverMinSegment(distance,puit.getChemin());
		chemin.add(0,tmp);
		while(!trouve){
			if(tmp.getPolygones().contains(source.getId())){
				trouve = true;
			}else{
				tmp = trouverMinSegment(distance,tmp.getCroisements());
				chemin.add(0,tmp);
			}
		}
		chemin.add(0,source);
		return chemin;
	}

	private Segment trouverMinSegment(double [] distance , List<Integer> leschemins){
		double min = distance[leschemins.get(0)];
		Segment s = this.chemins.get(leschemins.get(0));
		for(int i =  1 ; i < leschemins.size(); i++){
			if(distance[leschemins.get(i)] < min){
				min = distance[leschemins.get(0)];
				s = this.chemins.get(leschemins.get(i));
			}
		}
		return s;
	}

	private Segment trouve_min(boolean [] parcouru, double [] distance){
		double min = Double.MAX_VALUE;
		int index = -1;
		for (int i = 0 ; i < distance.length ; i++){
			if(distance[i] < min && !parcouru[i]){
				min = distance[i];
				index = i;
			}

		}

		return this.chemins.get(index);

	}

	private boolean allParcouru(boolean [] parcouru){
		boolean allT ;
		int i = 0;

		do
		{
			allT = parcouru[i];
			i++;
		}while(allT && i < parcouru.length);

		return allT;
	}

	public HashMap<Integer, Polygon> getPolygones() {
		return polygones;
	}

	public void setPolygones(HashMap<Integer, Polygon> polygones) {
		this.polygones = polygones;
	}

	public HashMap<Integer, Segment> getChemins() {
		return chemins;
	}

	public void setChemins(HashMap<Integer, Segment> chemins) {
		this.chemins = chemins;
	}

/*
	
	public static void main(String [] args){


		List<Segment> segments = new ArrayList<Segment>();

		// Segment A - B traverse
		Point deb = new Point(150, 100);
		Point fin = new Point(300,100);
		Segment s = new Segment(0,deb, fin);

		segments.add(s);

		//segment coupe C
		deb = new Point(225, 100);
		fin = new Point(225,300);
		s = new Segment(1,deb, fin);

		segments.add(s);


		//segment A-D
		deb = new Point(100, 150);
		fin = new Point(100,175);
		s = new Segment(2,deb, fin);

		segments.add(s);
		
		//segment contour A1 
		deb = new Point(175, 100);
		fin = new Point(175,125);
		s = new Segment(3,deb, fin);

		segments.add(s);
		
		//segment A2
		deb = new Point(175,125);
		fin = new Point(100,125);
		s = new Segment(4,deb, fin);

		segments.add(s);
		
		List<Polygon> polys = new ArrayList<Polygon>();

		// Batiment A
		List<Point> poly = new ArrayList<Point>();
		Point x = new Point(50, 50);
		poly.add(x);
		x = new Point(150,50);
		poly.add(x);
		x = new Point(150,150);
		poly.add(x);
		x = new Point(50,150);
		poly.add(x);


		Polygon p = new Polygon(0,poly, "batiment");

		polys.add(p);

		// Batiment B 
		poly = new ArrayList<Point>();

		x = new Point(300, 50);
		poly.add(x);
		x = new Point(450,50);
		poly.add(x);
		x = new Point(450,150);
		poly.add(x);
		x = new Point(300,150);
		poly.add(x);

		p = new Polygon(1,poly, "piscine");

		polys.add(p);


		// Batiment C

		poly = new ArrayList<Point>();

		x = new Point(150, 300);
		poly.add(x);
		x = new Point(300,300);
		poly.add(x);
		x = new Point(300,400);
		poly.add(x);
		x = new Point(150,400);
		poly.add(x);

		p = new Polygon(2,poly, "test");

		polys.add(p);

		// Batiment D
		poly = new ArrayList<Point>();

		x = new Point(50, 175);
		poly.add(x);
		x = new Point(150,175);
		poly.add(x);
		x = new Point(150,275);
		poly.add(x);
		x = new Point(50,275);
		poly.add(x);

		p = new Polygon(3,poly, "Hotel");

		polys.add(p);

		// Batiment A ajoute le segment 0 et 2
		polys.get(0).addCheminSortie(segments.get(0));
		polys.get(0).addCheminSortie(segments.get(2));
		// Batiment B ajoute le segment 0
		polys.get(1).addCheminSortie(segments.get(0));
		// Batiment C ajoute le segments 1
		polys.get(2).addCheminSortie(segments.get(1));
		// Batiment D ajoute le segment 2
		polys.get(3).addCheminSortie(segments.get(2));
		
		// Segment 0 ajoute le segment 1
		segments.get(0).addCroisement(segments.get(1));
		segments.get(0).addCroisement(segments.get(3));

		
		// Segement 0 ajout le batiment A et B
		segments.get(0).addPoly(polys.get(0));
		segments.get(0).addPoly(polys.get(1));
		
		// Le segment 1 ajoute le batiment C
		segments.get(1).addPoly(polys.get(2));
		// Le segment 1 ajoute le chemin 0
		segments.get(1).addCroisement(segments.get(0));

		// Le segment 2 ajoute les Batiment A et D
		segments.get(2).addPoly(polys.get(0));
		segments.get(2).addPoly(polys.get(3));
		
		// Le segment 2 ajoute le segment 4
		segments.get(2).addCroisement(segments.get(4));

		// Le segment 3 ajoute les segments 4 et 0
		segments.get(3).addCroisement(segments.get(0));
		segments.get(3).addCroisement(segments.get(4));

		// Le segment 4 ajoute les segments 2 et 3
		segments.get(4).addCroisement(segments.get(2));
		segments.get(4).addCroisement(segments.get(3));
		
		Graphe graph = new Graphe(polys, segments);
		System.out.println(graph);

		Point a = new Point(47.8453124f, 1.9209160000000338f);
		Point b = new Point(47.34727960000001f,1.2640099000000191f);
		System.out.println("Distance : " + poids(a,b));
		System.out.println("Batiment D -> Batiment B");
		List<INoeud> ss = graph.plusCourtChemin(polys.get(0),polys.get(2));

/*
		for(INoeud inoeud : ss)
			System.out.println(inoeud);
			
	}
*/
	
}
